package dataS.graph;

import dataS.queue.MyQueue;
import dataS.stack.MyStack;


public class Graph {

    //顶点数组
    private Vertex[] verticesList;
     //邻接矩阵adjacent matrix
    private int[][] adjMat;
    //顶点的最大数目
    private int maxSize=10;
    //已经添加的顶点
    private int nVertext;

    //栈，dfs
    private MyStack stack;
    //队列
    private MyQueue queue;

    public Graph(){
        verticesList=new Vertex[maxSize];
        adjMat=new int[maxSize][maxSize];
        //初始化邻接矩阵，为0代表没有链接
        for (int i = 0; i < maxSize; i++) {
            for (int j = 0; j < maxSize; j++) {
                adjMat[i][j]=0;
            }
        }
        nVertext=0;
        stack=new MyStack(maxSize);
        queue=new MyQueue(maxSize);
    }
    /**
     * 添加顶点
     */
    public void addVertex(char lable){
        verticesList[nVertext++]=new Vertex(lable);
    }
    /**
     * 添加边
     */
    public void addEdge(int start,int end){
        adjMat[start][end]=1;
        adjMat[end][start]=1;
    }
    /**
     * 获得邻接的未访问过的节点,-1表示找不到
     */
    public int getUnvisitedVertex(int v){
        for(int i=0;i<nVertext;i++){
            if(adjMat[v][i]==1&&verticesList[i].isVisited==false)
                return i;
        }
        return -1;
    }
    public void dfs(){
        //首先访问0号顶点
        verticesList[0].isVisited=true;
        //显示该顶点
        displayVertex(0);
        //压入栈
        stack.push(0);
        while (!stack.empty()){
            int v=getUnvisitedVertex(stack.peek());
            if(v==-1){
                //找不到
                stack.pop();
            } else {
                verticesList[v].isVisited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
        //搜索完成以后复原
        for (int i = 0; i < nVertext; i++) {
            verticesList[i].isVisited=false;
        }

    }
    public void bfs(){
        //首先访问0号顶点
        verticesList[0].isVisited=true;
        //显示该顶点
        displayVertex(0);
        //添加到队列
        queue.insert(0);
        while (!queue.empty()){
            int v=getUnvisitedVertex(queue.peek());
            //添加未被访问的节点
            while (v!=-1){
                verticesList[v].isVisited=true;
                displayVertex(v);
                queue.insert(v);
                v=getUnvisitedVertex(queue.peek());
            }
            queue.remove();
        }
        //搜索完成以后复原
        for (int i = 0; i < nVertext; i++) {
            verticesList[i].isVisited=false;
        }

    }
    //最小生成树,链接每个顶点最少的连线，定点数-1
    public void mst(){
        //首先访问0号顶点
        verticesList[0].isVisited=true;

        //压入栈
        stack.push(0);
        while (!stack.empty()){
            int cur=stack.peek();

            int v=getUnvisitedVertex(stack.peek());
            if(v==-1){
                //找不到
                stack.pop();
            } else {
                verticesList[v].isVisited=true;
                stack.push(v);
                //打印路径
                displayVertex(cur);
                System.out.print("-");
                displayVertex(v);
                System.out.print(" ");

            }
        }
        //搜索完成以后复原
        for (int i = 0; i < nVertext; i++) {
            verticesList[i].isVisited=false;
        }

    }

    public void displayVertex(int v){
        System.out.print(verticesList[v].label+"");
    }
}
